package io.xxx;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

public class One {

    public static void main(String[] args) {
//        int[] result1 = twoSum(new int[]{2, 7, 11, 15}, 9);
//        System.out.println(Arrays.toString(result1));
//
//        int[] result2 = twoSum(new int[]{3, 2, 4}, 6);
//        System.out.println(Arrays.toString(result2));
//
//        int[] result3 = twoSum(new int[]{3, 3}, 6);
//        System.out.println(Arrays.toString(result3));

//        int result1 = reverse(123);
//        System.out.println(result1);
//        int result2 = reverse(-123);
//        System.out.println(result2);
//        int result3 = reverse(120);
//        System.out.println(result3);
//        int result4 = reverse(0);
//        System.out.println(result4);

//        boolean result1 = isPalindrome(121);
//        System.out.println(result1);
//        boolean result2 = isPalindrome(-121);
//        System.out.println(result2);
//        boolean result3 = isPalindrome(10);
//        System.out.println(result3);
//        boolean result4 = isPalindrome(-101);
//        System.out.println(result4);
//        boolean result5 = isPalindrome(0);
//        System.out.println(result5);

//        System.out.println(romanToInt("III"));
//        System.out.println(romanToInt("IV"));
//        System.out.println(romanToInt("IX"));
//        System.out.println(romanToInt("LVIII"));
//        System.out.println(romanToInt("MCMXCIV"));

//        System.out.println(longestCommonPrefix(new String[]{"flower", "flow", "flight"}));
//        System.out.println(longestCommonPrefix(new String[]{"dog", "racecar", "car"}));

        System.out.println(isValid("()"));
        System.out.println(isValid("()[]{}"));
        System.out.println(isValid("(]"));
        System.out.println(isValid("([)]"));
        System.out.println(isValid("{[]}"));
    }

    // 两数之和
    public static int[] twoSum(int[] nums, int target) {
        int h, t;
        for (int i = 0; i < nums.length - 1; i++) {
            h = i;
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    t = j;
                    return new int[]{h, t};
                }
            }
        }
        return new int[]{};
    }

    // 整数反转
    public static int reverse(int x) {
        int lower = Integer.MIN_VALUE / 10;
        int upper = Integer.MAX_VALUE / 10;
        int result = 0;
        while (x != 0) {
            if (result < lower || result > upper) {
                return 0;
            }
            result = result * 10 + x % 10;
            x /= 10;
        }
        return result;
    }

    // 回文数
    public static boolean isPalindrome(int x) {
        if (x == 0) {
            return true;
        }
        if (x < 0 || x % 10 == 0) {
            return false;
        }

        int rev = 0;
        int dup = x;
        while (x != 0) {
            rev = rev * 10 + x % 10;
            x /= 10;
        }
        return rev == dup;
    }

    // 罗马数字转整数
    public static int romanToInt(String s) {
        Map<Character, Integer> symbols = new HashMap<>() {{
            put('I', 1);
            put('V', 5);
            put('X', 10);
            put('L', 50);
            put('C', 100);
            put('D', 500);
            put('M', 1000);
        }};
        int result = 0;
        int prev = symbols.get(s.charAt(0));
        for (int i = 1; i < s.length(); i++) {
            int cur = symbols.get(s.charAt(i));
            if (prev < cur) {
                result -= prev;
            } else {
                result += prev;
            }
            prev = cur;
        }
        result += prev;
        return result;
    }

    public static String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        String result = strs[0];
        for (int i = 1; i < strs.length; i++) {
            result = longestCommonPrefix(result, strs[i]);
        }
        return result;
    }

    public static String longestCommonPrefix(String str1, String str2) {
        int length = Math.min(str1.length(), str2.length());
        int index = 0;
        while (index < length) {
            if (str1.charAt(index) != str2.charAt(index)) {
                break;
            }
            index++;
        }
        return str1.substring(0, index);
    }

    // 有效的括号
    public static boolean isValid(String s) {
        if (s.length() % 2 == 1) {
            return false;
        }
        Map<Character, Character> map = new HashMap<>() {{
            put(')', '(');
            put(']', '[');
            put('}', '{');
        }};
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (map.containsKey(c)) {
                if (stack.isEmpty() || stack.peek() != map.get(c)) {
                    return false;
                }
                stack.pop();
            } else {
                stack.push(c);
            }
        }
        return stack.isEmpty();
    }
}
